package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class Pra10 {
    //最小计算次数问题
    /* 
        剪枝条件：
        (1) cur > target, 减去左分支；
        (2) cur < target, ...
        (3) times > min, 回溯
        (4) Set.contains(cur), 回溯 //已经解过这个方式
    */

    /* 
        计算方式0：cur*3
                1:cur/2
    */
    public int mininumCalculate(int num, int target) {
        // System.out.println(res);
        dfs(num, target, 0,new ArrayList<>(), new HashSet<>());
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    int min = Integer.MAX_VALUE;
    List<Integer> res = new ArrayList<>();

    public void dfs(int cur, int target, int times, List<Integer> path, Set<Integer> set) {
        if (cur == target) {
            min = Math.min(min, times);
            System.out.println();
            System.out.println("一种算法是：");
            for (int i = 0; i < path.size(); i++) {
                String s = path.get(i) == 0 ? "乘以3" : "除以2";
                System.out.println("第"+(i+1) + "步：" + s);
            }
            return;
        }
        if (set.contains(cur) || times >= min)
            return;
        set.add(cur);
        if (cur < target) {
            path.add(0);
            dfs(cur * 3, target, times + 1, path, set);
        } else {
            path.add(1);
            dfs(cur / 2, target, times + 1, path, set);
        }
        path.remove(path.size() - 1);
        set.remove(cur);
    }

    @Test
    public void test() {
        System.out.println(mininumCalculate(2, 9));
    }
}
